#include <vector>
using namespace std;
/**
 * height =             [ 0 , 1 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ]     每个柱子的高度
 * max_L                [ 0 , 1 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 , 3 ]     每个柱子左侧的最高柱子(包含自身)
 * max_R                [ 3 , 3 , 3 , 3 , 3 , 3 , 3 , 2 , 2 , 2 , 1 ]     每个柱子右侧的最高柱子(包含自身)
 * min(max_L, max_R)    [ 0 , 1 , 2 , 2 , 2 , 2 , 3 , 2 , 2 , 2 , 1 ]     每个柱子两侧最高柱子的较小值
 * area[i]          = min(max_L, max_R) - height
 *                      [ 0 , 0 , 0 , 1 , 2 , 1 , 0 , 0 , 1 , 0 , 0 ]     每个柱子能接的雨水
 */
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int left = 0;                  // 左指针
        int right = height.size() - 1; //   右指针
        int maxL = height[left];       // 左侧最高柱子高度
        int maxR = height[right];      //  右侧最高柱子高度
        int res = 0;
        while (left <= right)
        {
            maxL = max(maxL, height[left]);  // 更新左侧最高柱子高度
            maxR = max(maxR, height[right]); // 更新右侧最高柱子高度
            if (maxL < maxR)
            {
                res += (maxL - height[left]); // 计算左侧能接的雨水
                ++left;
            }
            else
            {
                res += (maxR - height[right]); // 计算右侧能接的雨水
                --right;
            }
        }
        return res;
    }
};